package stack;

import java.util.*;

/**
 * 最小栈
 * 在常数时间检测到最小元素，每增加或者删除一个元素，
 * 都能以常数时间获得栈中的最小值<p>
 * 如果我要在O(1)时间内得到最大值呢？
 */
public class MinStack {

  /**
   * 使用两个双端队列Deque来完成
   */
  class MinStack1 {
    //存储数据
    Deque<Integer> stack;

    //存储截止到当前元素，栈中的最小元素
    Deque<Integer> minStack;

    public MinStack1() {
      stack = new LinkedList<>();
      minStack = new LinkedList<>();
    }

    public void push(int x) {
      //要个栈要么都是空的，要么都有元素
      if (stack.isEmpty() && minStack.isEmpty()) {
        minStack.offerFirst(x);
      } else {
        minStack.offerFirst(Math.min(stack.peekFirst(), x));
      }
      stack.offerFirst(x);
    }

    public void pop() {
      if (!stack.isEmpty() && !minStack.isEmpty()) {
        stack.pollFirst();
        minStack.pollFirst();
      }
    }

    public int top() {
      return stack.isEmpty() ? -1 : stack.peekFirst();
    }

    public int getMin() {
      return minStack.isEmpty() ? -1 : minStack.peekFirst();
    }

  }

  /**
   * 使用一个List来完成
   */
  class MinStack2 {
    private List<Integer> list;

    public MinStack2() {
      this.list = new ArrayList<>();
    }

    public void push(int x) {
      this.list.add(x);
    }

    public void pop() {
      if (this.list.size() == 0) {
        return;
      } else {
        this.list.remove(this.list.size() - 1);
      }
    }

    public int top() {
      if (this.list.isEmpty()) {
        return Integer.MIN_VALUE;
      } else {
        return this.list.get(this.list.size() - 1);
      }
    }

    public int getMin() {
      if (this.list.isEmpty()) {
        return Integer.MIN_VALUE;
      }
      Object[] objects = list.toArray();
      Arrays.sort(objects);
      return (Integer) objects[0];
    }
  }
}
